#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> phone_map = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
        vector<string> result;
        string current;
        backtrack(digits, 0, phone_map,result,current);
        return result;
    }
private:
    void backtrack(const string& digits, int index,const vector<string>& phone_map, vector<string>& result, string& current) {
        if (index == digits.size()) { result.push_back(current); return; }
        int digit = digits[index] - '0';
        const string& letters = phone_map[digit];
        for (char letter : letters) {
            current.push_back(letter);
            backtrack(digits, index + 1, phone_map, result, current);
            current.pop_back();
        }
    }
};